The present invention is directed to communications networking and in particular to networks that employ label switching.
Internetwork communications are based on operations of routers, which are network devices that determine, on the basis of destination information in packets that they receive, where to forward the packets so that they are likely to reach the intended destinations.
Router configurations vary widely, but FIG. 1 depicts a typical approach. Router 10 includes a plurality of communications interfaces 12, 14, and 16, which send and receive communications packets to and from remote locations. When one of the interface modules receives an incoming packet, it places header information from that packet onto an internal communications bus 18 by which it communicates with a forwarding engine 20, typically a high-performance processor configured by instructions in associated storage circuitry, that determines where the packet should be sent. Once the decision has been made, an output packet is formed from the input packet by packet assembly circuitry that may reside in one or more of the interface modules and the forwarding engine, and the forwarding engine operates another interface to cause it to send the output packet to a further remote location.
FIG. 2 depicts the router 10 in a local-network environment in which it communicates through one of its interfaces to such remote locations by way of a local-area-network bus 22. In a link of that nature, there are typically a number of network devices, such as network devices 24, 26, 28, and 30, that receive the resultant packet-bearing signals, but the packet is not usually intended for all of them. Different systems employ different packet formats to enable their various network devices to distinguish the packets they should read from the ones they should not, but the Ethernet packet format of FIG. 3 is typical.
In that drawing, each packet begins with a link-layer header 32. The link-layer header includes, among other fields, a field that contains a link-layer destination address. If the destination address does not match the address of a network-device interface that receives the packet, that network device ignores the packet.
For present purposes, we will assume that router 10 intends the packet to be received by a further router 30, so the link-layer header""s destination-address field will contain the link-layer address of router 30""s interface with network link 22. That interface accordingly reads the remainder of the packet,,verifying that the contents of a cyclic-redundancy-code trailer 34 are consistent with the remainder of the packet. It then proceeds to process the link-layer packet""s payload 36 in accordance with a protocol that the link-layer header""s type field specifies.
In the present case, the type field specifies that the link-layer packet""s payload is an Internet Protocol (xe2x80x9cIPxe2x80x9d) datagram, which is a network-layer protocol data unit. The purpose of the router""s IP process is to determine how to forward the datagram to its ultimate (internetwork-host) destination. To make this determination, the IP process inspects the IP datagram""s header 38, and in particular its IP destination-address field. That field""s contents identify the host system to which the datagram""s contents are to be directed, and router 30 uses this address to determine through which of its interfaces to forward the packet on to that host system.
The router makes this determination by using a forwarding table, into which it has distilled information about internetwork topology that it has typically obtained by communications with other routers. Routers inform other routers of the host systems to which they can forward communications packets, and they employ such information obtained from other routers to populate their forwarding tables.
Now, the IP address is 32 bits long in most versions and even longer in versions that will soon be adopted, so the IP address could theoretically distinguish among over four billion host systems. Actually, the number of host systems that have globally unique IP addresses is much smaller that this, but the number still is much greater than it is practical for an individual router to have route entries for in its forwarding table.
The solution to this problem historically has been to base the table look-up on destination-address prefixes. That is, some routers will simply indicate that they can handle traffic to all hosts whose destination addresses begin with a particular, say, 16-bit sequence, or xe2x80x9cprefix.xe2x80x9d Additionally, a router may compact its information so as to store routes in this form. Prefixes vary in length, the longest being the most specific and thus presumably representing the best routes to the included host addresses. So when a router receives an IP datagram, it searches through the prefix entries in the forwarding table to find the longest-prefix that matches the incoming packet""s destination address. When it finds that route in its forwarding table, it reads that route""s fields that specify the interface over which it should forward the packet and the link-layer address of the router to which the interface should send the packet for further forwarding.
Although this approach has proved quite serviceable and robust, it has exhibited shortcomings that have led some workers to propose a table-index-based forwarding approach for high-speed networks such as those of some Internet-service providers (xe2x80x9cISPsxe2x80x9d). Specifically, routers would inform their neighbor routers of the locations within their tables at which the routes to particular prefixes are located. When their neighbors send them packets destined for those prefixes, those neighbors insert a xe2x80x9cshimxe2x80x9d between the link-layer header (such as an Ethernet header) and the network-layer header (typically, an IP header). This shim""s contents include a label (also referred to as a xe2x80x9ctagxe2x80x9d) that is an index to the desired route in the receiving router""s forwarding table.
One of this approach""s advantages is that it relieves the receiving router of the need to perform an expensive longest-match search: the label points the receiving router directly to the correct forwarding-table entry. Commonly assigned co-pending U.S. patent application Ser. No. 08/997,343, filed on Dec. 23, 1997 now U.S. Pat. No. 6,339,545, by Rekhter et al. for Peer Model Support for Virtual Private Networks with Potentially Overlapping Addresses, describes in detail one proposal, known as Multiple-Protocol Label Switching (xe2x80x9cMPLSxe2x80x9d), for employing such shims. That application also includes an exemplary protocol, referred to as the Tag Distribution Protocol (xe2x80x9cTDPxe2x80x9d) by which routers inform their neighbors of the labels that they associate with their forwarding-table entries. I hereby incorporate that application in its entirety by reference.
FIG. 4 depicts the resultant packet format. The link-layer header has the same format as in FIG. 3, but its type field identifies the link-layer payload as beginning not with an IP header but rather with an MPLS header, or xe2x80x9cshimxe2x80x9d between the link-layer header and the network-layer header. FIG. 4 illustrates the MPLS header""s format. The MPLS header is organized as a stack of entries, and FIG. 4 gives an example in which there are two entries 40 and 42. In addition to other information, each entry includes a label, which is an index into the forwarding table of the label-switching router that receives it. When a router receives such a packet, it consults the forwarding-table entry that the label specifies and replaces that label with a replacement label that the specified forwarding-table entry contains. That replacement label is typically one that the next router on the path to the requested destination has asked to be included in packets sent to it and intended for the destination with which the forwarding table is associated. For reasons that will become apparent below, the MPLS header may contain more than one label, and the end-of-stack (xe2x80x9cSxe2x80x9d) bit in a stack entry indicates whether it is the bottom entry in the stack. That bit is not set in FIG. 4""s entry 40, so that the stack entry is not the bottom one, but it is set in entry 42, which therefore is the bottom stack entry.
Although the formats described in FIGS. 3 and 4 are typical formats for packets exchanged between label-switching routers, they are not the only formats that such routers employ. Routers that communicate with each other over a point-to-point link, i.e., not by way of a shared medium, typically would employ a link-level protocol different from the Ethernet protocol just described, and the formats employed on some xe2x80x9cEthernetxe2x80x9d links are actually somewhat more complicated than the format depicted here. In addition, packet forwarding often occurs by way of Asynchronous Transfer Mode (xe2x80x9cATMxe2x80x9d) links.
In the case of label-switching routers implemented in ATM switches, the IP datagrams are encapsulated in ATM frames. FIG. 5""s third row depicts an ATM frame, and its fourth and fifth rows show that the frame""s payload is similar to the IP datagram and shim header that FIG. 4""s Ethernet header and trailer encapsulate. The only difference is that FIG. 5""s fifth row represents the top label by question marks, which indicate that the top label""s contents do not matter.
The reason why they do not is that the routing decisions based on those contents when the label-switching router is implemented as a conventional IP router are instead based on an ATM VPI/VCI field in the header of an ATM xe2x80x9ccellxe2x80x9d when the label-switching router is implemented as an ATM switch. From the point of view of an ATM client, the frame of FIG. 5""s third row is the basic unit of transmission, and it can vary in length to as much as 64 Kbytes of payload. (Those skilled in the art will recognize that there are also other possible ATM frame formats, but FIG. 5""s third row depicts one, known as xe2x80x9cAAL5,xe2x80x9d that would typically be employed for user data.) From the ATM switch""s point of view, though, the basic transmission units are fixed-size cells into which the frames are divided.
Each cell consists of a header and a payload, as FIG. 5""s second row illustrates. Among the purposes of the header""s PTI field, depicted in FIG. 5""s first row, is to indicate whether the cell is the last one in a frame. If it is, its last eight bytes form the frame trailer field that FIG. 5""s third row depicts. Among other things, the trailer indicates how much of the preceding cell contents are actual payload, as opposed to padding used to complete a fixed-size cell.
The header field of interest to the present discussion is the VPI/VCI field of FIG. 5""s first row. As is well known to those skilled in the art, ATM systems organize their routes into xe2x80x9cvirtual channels,xe2x80x9d which may from time to time be grouped into xe2x80x9cvirtual paths.xe2x80x9d Each switch associates a local virtual path/virtual channel indicator (VPI/VCI) with a channel or path that runs through it. When an ATM switch receives a cell, it consults the cell""s VPI/VCI field to identify by table lookup the interface through which to forward the cell. It also replaces that field""s contents with a value indicated by the table as being the next switch""s code for that path or channel, and it sends the resultant cell to the next switch. In other words, the function performed by the VPI/VCI field enables it to serve as the stack""s top label. This is why a label-switching router implemented as an ATM switch can ignore the top label field, on which other implementations rely.
It is desirable to use ATM switches in high-volume, xe2x80x9cbackbonexe2x80x9d routers: their fixed cell sizes and use of virtual-channel indicators make it possible for them to operate very rapidly, as is desirable in high-bandwidth backbone networks. Because of the hardware ordinarily employed to implement them, though, ATM switches are subject to one particular drawback, and that is the size of the potential VCI space: the number of VCIs that a given ATM switch can have committed at any one time is relatively small. When a first ATM switch is to forward to a second ATM switch a packet intended for a new destination, the first switch asks the second switch to allocate a VCI for use by that first switch in sending the second switch any packets intended for that destination. Consequently, if the switch is interconnected with many other switches, all of which need its services to forward packets to many different destinations, the switch may be called on to allocate a number of VCIs that exceeds its capacity. Even in systems that do not employ ATM switches to implement label-switching routers, the memory capacity required for a large number of forwarding-information-base entries can be costly.
Proposals have been made to limit forwarding-table size by employing multi-level labeling. This is a type of tunneling, in which the packet being forwarded includes one or more labels representing intermediate destinations, typically in addition to a xe2x80x9cbottomxe2x80x9d label representing the ultimate destination. To forward such packets, switches along the route to the intermediate destination need not have allocated labels to the ultimate destination. The Rekhter et al. application described above sets forth an example by which, say, a service provider""s edge routerxe2x80x94i.e., a router with a link to one of the service provider""s customersxe2x80x94attaches a top label requesting the route to another edge router as well as a bottom label representing the destination in the customer""s network.
I have recognized that a further reduction in required label space can be achieved by taking advantage of the area concept employed by Open Shortest Path First (xe2x80x9cOSPFxe2x80x9d), a protocol popularly employed by routers within an autonomous system to exchange the topological information on which they base their routing decisions. Routers in a commonly administered group of networks conventionally employ OSPF to maintain a consistent view of the topology within that group of routers, which we will refer to as a xe2x80x9crouting domain.xe2x80x9d Although the general intention of OSPF is for all of its routers to maintain a common map of the networks within the routing domain, routers in many existing OSPF domains are sometimes configured to divide the domain into xe2x80x9careasxe2x80x9d between which there are topological-information differences. Specifically certain routers have links to more than one area and are configured to consider themselves xe2x80x9carea border routers.xe2x80x9d Such routers export only a summary of one area""s detailed topological information into another area, and this reduces the amount of topological information the various areas must maintain in order to perform their routing functions adequately.
I have recognized that a further reduction in required label space can be achieved by taking advantage of the area concept employed by Open Shortest Path First (xe2x80x9cOSPFxe2x80x9d), a protocol popularly employed by routers within an autonomous system to exchange the topological information on which they base their routing decisions. Routers in a commonly administered group of networks conventionally employ OSPF to maintain a consistent view of the topology within that group of routers, which we will refer to as a xe2x80x9crouting domain.xe2x80x9d Although the general intention of OSPF is for all of its routers to maintain a common map of the networks within the routing domain, routers in many existing OSPF domains are sometimes configured to divide the domain into xe2x80x9careasxe2x80x9d between which there are topological-information differences. Specifically, certain routers have links to more than one area and are configured to consider themselves xe2x80x9carea border routers.xe2x80x9d Such routers export only a summary of one area""s detailed topological information into another area, and this reduces the amount of topological information the various areas must maintain in order to perform their routing functions adequately.